package com.leetcode.partition14;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/26 17:16
 */
public class LC1314矩阵区域和 {

    public static int[][] matrixBlockSum(int[][] mat, int k) {
        return dynamicProgramming(mat, k);
    }

    public static void main(String[] args) {
        int[][] mat = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        mat = matrixBlockSum(mat, 1);
        System.out.println();
        Arrays.stream(mat).forEach(val -> System.out.println(Arrays.toString(val)));
    }

    private static int[][] dynamicProgramming(int[][] mat, int k) {
        //矩阵前缀和，dp[i][j]表示mat[0][0]到mat[i-1][j-1]的矩阵之和
        int[][] dp = new int[mat.length + 1][mat[0].length + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                //减去dp[i-1][j-1]是因为在加dp[i-1][j]和dp[i][j-1]时重复了一次，需要减去
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        //计算以 (i-k, j-k) 为左上角，(i+k, j+k) 为右下角之和
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                int downIndex = Math.min(i + k + 1, dp.length - 1);
                int rightIndex = Math.min(j + k + 1, dp[0].length - 1);
                int upIndex = Math.max(0, i - k);
                int leftIndex = Math.max(0, j - k);
                //加上dp[upIndex][leftIndex]是因为在减dp[upIndex][rightIndex]和dp[downIndex][leftIndex]时重复减去了一次
                mat[i][j] = dp[downIndex][rightIndex] - dp[upIndex][rightIndex] - dp[downIndex][leftIndex] + dp[upIndex][leftIndex];
            }
        }
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return mat;
    }
}
